<textarea id='src'>
a
aa
aaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaa
aa
a
</textarea>
<textarea id='dst'>
a
aa
aaab
aaaab
aaab
aa
ab
aab
aaa
aaaa
aaa
aab
ab
aa
aaab
aaaab
aaab
aa
ab
aab
aaa
aaaa
aaa
aab
ab
a
aa
aaa
bbbb
aaa
aa
ab
aab
aaa
aaaa
aaa
aab
ab
a
</textarea>
<button onclick='diff();'>diff</button>
<hr />
<div id='result'></div>
<script>

var sed = {
	_sLen : -1,
	_dLen : -1,
	_shortcutNode : [],
	setUp : function(arrSrc, arrDst) {
		/*
			arrSrc : [a, b, c, d, e]
			arrDst : [a, b, d, a]

			   0:- 1:a 2:b 3:d 4:a
			0:-┌─┬─┬─┬─┐
			   │＼│  │  │＼│
			1:a├─┼─┼─┼─┤
			   │  │＼│  │  │
			2:b├─┼─┼─┼─┤
			   │  │  │  │  │
			3:c├─┼─┼─┼─┤
			   │  │  │＼│  │
			4:d├─┼─┼─┼─┤
			   │  │  │  │  │
			5:e└─┴─┴─┴─┘

			in this case, shortcut :

				(0, 0) --> (1, 1)
				(0, 3) --> (1, 4)
				(1, 1) --> (2, 2)
				(3, 2) --> (4, 3)

			in this case,

				this._sLen : 6
				this._dLen : 5
				this._shortcutNode : [
					[0, 3],
					[1],
					[],
					[2],
					[],
					[] // dummy
				]
		*/
		for (var i = 0; i < arrSrc.length; i++) {
			this._shortcutNode[i] = [];
			for (var j = 0; j < arrDst.length; j++) {
				if (arrSrc[i] == arrDst[j]) {
					this._shortcutNode[i].push(j);
				}
			}
		}
		this._shortcutNode.push([]);
		this._sLen = arrSrc.length + 1;
		this._dLen = arrDst.length + 1;
	},
	// (ixs, ixd) より左下方向のショートカット確認
	shortcutIsExist : function(ixs, ixd) {
		for (var i = ixs; i < this._sLen; i++) {
			var node = this._shortcutNode[i];
			for (var j = 0; j < node.length; j++) {
				if (node[j] >= ixd) {
					return true;
				}
			}
		}
		return false;
	},
	// 始点 (ixs1, ixd1) から終点 (ixs2, ixd2) のショートカットを用いない経路配列。始点は含まない
	edgeRoute : function(ixs1, ixd1, ixs2, ixd2) {
		var route = [];
		// d（右）方向
		for (var j = ixd1 + 1; j <= ixd2; j++) {
			route.push({s : ixs1, d : j, c : 1});
		}
		// s（下）方向
		for (var i = ixs1 + 1; i <= ixs2; i++) {
			route.push({s : i, d : ixd2, c : -1});
		}
		return route;
	},
	// 始点 (ixs, ixd) からの連続したショートカットの配列。始点は含まない
	shortcutRoute : function(ixs, ixd) {
		var node = this._shortcutNode[ixs];
		for (var j = 0; j < node.length; j++) {
			if (node[j] == ixd) {
				return ([{s : ixs + 1, d : ixd + 1, c : 0}]).concat(this.shortcutRoute(ixs + 1, ixd + 1));
			} else if (node[j] > ixd) {
				break;
			}
		}
		return [];
	},
	isCandidate : function(ixs, ixd) {
		var N = 5;
		var f = ixd - ixs;
		if ((0 < f + N) && (f - N < 0)) {
			return true;
		}
		return false;
	},
	// 始点 (ixs, ixd) から d（右）方向に移動し終点までのコスト計算
	findRoute2Dst : function(ixs, ixd) {
		var route = [];
		for (var j = ixd; j < this._dLen - 1; j++) {
			if (!this.isCandidate(ixs, j)) {
				return route.concat(this.edgeRoute(ixs, j, this._sLen - 1, this._dLen - 1));
			} else {
				var sarr = this.shortcutRoute(ixs, j);
				if (sarr.length == 0) {
					route.push({s : ixs, d : j + 1, c : 1});
				} else {
					route = route.concat(sarr);
					var edge = sarr[sarr.length - 1];
					return route.concat(this.findRoute2Src(edge.s, edge.d));
				}
			}
		}
		// ショートカットなく左端に達した場合
		if (ixs < this._sLen - 1) {
			return route.concat(this.edgeRoute(ixs, this._dLen - 1, this._sLen - 1, this._dLen - 1));
		} else {
			return route;
		}
	},
	/*
		始点 (ixs, ixd) から s（下）方向に

			1) (ixs,     ixd)
			2) (ixs + 1, ixd)
			3) (ixs + 2, ixd)
			...

		で右折する経路のコストを逐次計算し、最小コストの経路配列（始点は含まない）を返す
	*/
	findRoute2Src : function(ixs, ixd) {
		var cand = [];
		for (var i = ixs; i < this._sLen; i++) {
			if (!this.isCandidate(i, ixd)) {
				break;
			}
			var ix = i - ixs;
			if (i == ixs) {
				cand[ix] = [];
			} else {
				// i > ixs の場合は d（右）方向を走査する前に s（下）方向のコスト計算
				cand[ix] = this.edgeRoute(ixs, ixd, i, ixd);
			}
			if (this.shortcutIsExist(i, ixd)) {
				cand[ix] = cand[ix].concat(this.findRoute2Dst(i, ixd));
			} else {
				cand[ix] = cand[ix].concat(this.edgeRoute(i, ixd, this._sLen - 1, this._dLen - 1));
				break;
			}
		}
		var min = {
			cost : Number.MAX_VALUE,
			ix : -1
		};
		for (var k = 0; k < cand.length; k++) {
			var ro = cand[k];
			var cost = 0;
			for (var l = 0; l < ro.length; l++) {
				cost += Math.abs(ro[l].c);
			}
			if (cost < min.cost) {
				min.cost = cost;
				min.ix = k;
			}
		}
		if (min.ix >= 0) {
			return cand[min.ix];
		} else {
			return [];
		}
	},
	diff : function(arrSrc, arrDst) {
		this.setUp(arrSrc, arrDst);
		var route = this.findRoute2Src(0, 0);
		var lines = [];
		for (var k = 0; k < route.length; k++) {
			switch (route[k].c) {
			case 0 :
				lines.push({data : arrSrc[route[k].s - 1], diff : null});
				break;
			case -1 :
				lines.push({data : arrSrc[route[k].s - 1], diff : '-'});
				break;
			case 1 :
				lines.push({data : arrDst[route[k].d - 1], diff : '+'});
				break;
			default :
				break;
			}
		}
		return lines;
	}
};

String.prototype.toLines = function() {
	return this.replace(/^\s+|\s+$/g, '').split("\n");
}

function diff()
{
	var arrSrc = document.getElementById('src').value.toLines();
	var arrDst = document.getElementById('dst').value.toLines();
	var start = +new Date;
	var lines = sed.diff(arrSrc, arrDst);
	var html = '<div>time : ' + ((+new Date) - start) + '</div><br />';
	var row = function(diff, src, dst) {
		return '<tr><td>' + diff + '</td><td>' + src + '</td><td>' + dst + '</td></tr>';
	};
	html += '<table>';
	for (var i = 0; i < lines.length; i++) {
		var l = lines[i];
		switch (l.diff) {
		case '+' :
			html += row(l.diff, '', l.data);
			break;
		case '-' :
			html += row(l.diff, l.data, '');
			break;
		default :
			html += row('', l.data, l.data);
			break;
		}
	}
	html += '</table>';
	document.getElementById('result').innerHTML = html;
}

</script>
<style type='text/css'>
TABLE {border-collapse: collapse;}
TABLE, TD {border: solid 1px black;}
TEXTAREA {width: 40%; height: 10em;}
</style>
